package chapter01.problem05;

import java.util.Stack;

public class SortStackInSpace {

	public static void sortStack(Stack<Integer> stack){
		if(stack.isEmpty())
			return;
		int min = stack.pop();
		//得到当前栈中的最小元素并从栈中删除。
		int i = getAndRemoveMin(stack, min);
		//递归调用
		sortStack(stack);
		//将最小值压栈。
		stack.push(i);
	}
	/**
	 * 辅助函数，得到并删除栈中最小的元素，然后将其返回。
	 * @param stack
	 * @param min
	 * @return
	 */
	private static int getAndRemoveMin(Stack<Integer> stack, int min) {
		if(stack.isEmpty())
			return min;
		Integer pop = stack.pop();
		if(pop<min){
			int temp = min;
			min=pop;
			pop=temp;
		}
		min = getAndRemoveMin(stack, min);
		stack.push(pop);
		return min;
	}
	
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(3);
		stack.push(2);
		stack.push(2);
		stack.push(4);
		stack.push(5);
		stack.push(1);
		System.out.println(stack);
		SortStackInSpace.sortStack(stack);
		System.out.println(stack);
	}
}
